package com.jhy.review.day02;

/**
 * 找一个节点的后继节点
 * 中序遍历后按位置排列
 * 由于我们要有父指针这个节点 所以我们就不用使用中序遍历然后用集合来存放 算出节点的后继节点。使用例外的一个方法
 * 我们分为两种情况
 * 1）一个节点当中的树，这个x节点否有右树 如果有右树，后继节点是右树最最左节点。
 * 2）一个当前节点没有右树，那么就去寻找节点的父节点 如果发现当前节点是父节点的左孩子，那么该节点的下一节点为父节点
 * 还有一种特殊情况 就是没有右树的最后一个节点的下一个节点为null。也可以直接向父节点放回 直到父节点为null。那么就是这个父节点的值。
 */
public class FindSuccessorNode {
    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node process(Node node) {
        if (node == null) {
            return node;
        }

        // 第一种情况
        if (node.right != null) {
            return getLeftNode(node.right);
        }
        // 第二种情况
        // 先求出该节点的父节点
        Node parent = node.parent;
        // 如果parent不为空 并且当前孩子不是父亲的左孩子 就一直循环下去。
        while (parent != null && parent.left != node) {
            // parent 赋值为当前孩子
            node = parent;
            // parent 为当前 节点的父节点
            parent = node.parent;
        }
        // 这个放回有两种结果 一种是一旦发现当前孩子是父节点的左孩子 那么放回这个父亲 就是当前孩子的下一节点。
        // 第二种就是发现父节点为空了 那么就放回这个父节点 也为null。
        return parent;

    }

    public static Node getLeftNode(Node node) {
        if (node == null) {
            return node;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }


}


